#include "single_array.h"
int array[ARRAY_MAX_LEN]={0};

void print_array(int *array,int len)
{
	if(len<=0)
		printf("数组长度为0,无法打印！\n");

	for(int i=0;i<len;i++)
	{
		printf("array[%d]=%d \t",i,array[i]);
		if((i+1)%10==0)
			printf("\n");	
	}
	printf("\n数组长度是：%d \n",len);	
}

int delete_single_array(int *array,int len)
{
	memset(array,0,len*4);  //此函数按字节个数清零
	return 0;
}

int  auto_create_single_array(int *array)
{
	int i, b;
	int len,start,end;
	//int array[ARRAY_MAX_LEN]={0};
	printf("请输入数组长度：\n");
	scanf("%d",&len);
	printf("请输入数据最小值：\n");
	scanf("%d",&start);
	printf("请输入数据最大值：\n");
	scanf("%d",&end);
	if(end<start)
	{
		printf("最大值小于最小值，无法创建！");
		return 0;		
	}

	if(len>ARRAY_MAX_LEN)
	{
		printf("长度大于10000，无法创建");
		return 0;
	}
	srand((int)time(0));
	for(i=0;i<len;i++)
	{
		b = rand() % end + start;
		array[i]=b;
	}
	printf("创建完成：\n");
	print_array(array,len);
	return len;
}

int self_create_single_array(int *array)
{
	int i, b,len;
	printf("请输入要创建的数组长度：");
	scanf("%d",&len);
	printf("\n");
	if(len>ARRAY_MAX_LEN)
	{
		printf("长度大于10000，无法创建");
		return 0;
	}
	
	for(i=0;i<len;i++)
	{
		printf("请输入要创建的数据：");
		scanf("%d",&b);
		array[i]=b;
		printf("\n");
	}
	printf("创建完成：\n");
	print_array(array,len);
	return len;
}
/***********交换排序*********start*****/
/*冒泡排序     start*/
void array_bubble_sort(int *a,int len)
{
	int tmp;
	int c=0;
	int l=0;
	for(int i=0;i<len-1;i++)
	{
		for(int j=0;j<len-1-i;j++)
		{
			if(a[j]>a[j+1])	
			{
				tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;			
				c++;			
			}		
			l++;
		}
		l++;
	}
	printf("冒泡排序交换%d次，循环%d次\n",c,l);
}
/*冒泡排序     end*/

/*
快速排序
*/
static int c=0;
static int l=0;
void array_quick_sort_sub(int *array,int left,int right)
{	
	int tmp,move;
	if(left>=right)
		return;
	move=left;
	for(int i=left;i<right;i++)
	{
		if(array[left]>array[i+1])
		{
			move++;
			tmp=array[move];
			array[move]=array[i+1];
			array[i+1]=tmp;
			c++;
		}
		l++;
	}	
	tmp=array[move];
	array[move]=array[left];
	array[left]=tmp;
	c++;
	array_quick_sort_sub(array,left,move);
	array_quick_sort_sub(array,move+1,right);	
}
void array_quick_sort(int *array,int len)
{	
/*	int i=0;
	while(1)
	{
		array_back[i]=array[i];
		i++;
		if(i==(len-1))
			break;
	}
	array_quick_sort_sub(array_back, 0,len-1);
*/
	array_quick_sort_sub(array, 0,len-1);
	printf("快速排序交换%d次，循环%d次\n",c,l);
}

void single_array_swap_sort(int *array,int len)
{
	int n;
back:
	printf("1.冒泡排序\n");
	printf("2.快速排序\n");
	printf("3.退出\n");
	printf("\n请输入数字：");
	scanf("%d",&n);
	if(n==1)
		array_bubble_sort(array,len);
	else if(n==2)
		array_quick_sort(array,len);
	else if(n==3)
		return;
	else
		goto back;
}
/**************end*******************/


/***********插入排序**************/
void simple_insert_sort(int *array,int len)
{
	int tmp,current;
	int c=0;
	int l=0;
	for(int i=1;i<len;i++)
	{
		if(array[i]<array[i-1])
		{
			tmp=i;
			current=array[i];
			while((tmp>0)&&(array[tmp-1]>current))
			{
				array[tmp]=array[tmp-1];
				tmp--;
				l++;
			}
			array[tmp]=current;
			c++;
		}
		l++;
	}
	printf("简单插入排序插入%d次，循环%d次\n",c,l);
}

void half_inserted_sort(int *array,int len)
{
	int low,high,mid,tmp;
	int l=0;
	int c=0;
	for(int i=1;i<len;i++)
	{
		low=0;
		tmp=array[i];
		high=i-1;
		while(high>=low)
		{
			mid=(low+high)/2;
			if(tmp>array[mid])
				low=mid+1;
			else
				high=mid-1;
			l++;
		}
		for(int j=i; j>low; j--)
		{
			array[j]=array[j-1];
			l++;
		}
		array[low]=tmp;
		c++;
		l++;
	}
	printf("折半插入排序插入%d次，循环%d次\n",c,l);
}
void shell_sort(int *array,int len)
{
	int current,increment;
	int c=0;
	int l=0;
	increment=len;
	do{
		increment=increment/3+1;
		for(int i=0+increment;i<len;i++)
		{
			if(array[i]<array[i-increment])
			{
				current=array[i];
				int j=i- increment;
				do{
						array[j+increment]=array[j];
						j=j-increment;
						l++;
				}while(j>=0&&array[j]>current);
				array[j+increment]=current;
				c++;
			}
			l++;
		}
	l++;
	}while(increment >1);
printf("希尔排序插入%d次，循环%d次\n",c,l);
}

void single_array_insert_sort(int *array,int len)
{
	int n;
back:
	printf("1.简单插入排序\n");
	printf("2.折半插入排序\n");
	printf("3.希尔排序\n");
	printf("4.退出\n");
	printf("\n请输入数字：");
	scanf("%d",&n);
	if(n==1)
		simple_insert_sort(array,len);
	else if(n==2)
		half_inserted_sort(array,len);
	else if(n==3)
		shell_sort(array,len);
	else if(n==4)
		return;
	else
		goto back;
} 
/*********************************/

/***********选择排序**************/
void simple_select_sort(int *array,int len)
{
	int i,j,tmp;
	int c=0;
	int l=0;
	for(i=0;i<len-1;i++)
	{
		for(j=i+1;j<len;j++)
		{
			if(array[i]>array[j])
			{
				tmp=array[i];
				array[i]=array[j];
				array[j]=tmp;
				c++;
			}
			l++;
		}
		l++;
	}
	printf("简单选择排序交换%d次，循环%d次\n",c,l);
}
static int loop=0;
static int swap=0;
void setup_heap(int *array,int start, int end)
{
	int tmp,i,j;
	tmp=array[start];
	i=2*start;
	while(i<=end)
	{
		loop++;
		if(i<end&&array[i]<array[i+1])
			i++;
		if(array[i]>tmp)
		{
			array[start]=array[i];
			start=i;
			i=2*i;
			swap++;
		}
		else
			break;
	}
	array[start]=tmp;
}
void heap_sort(int *array,int len)
{
	int a[ARRAY_MAX_LEN]={0};
	int n,j,i,tmp;
	i=0;
	while(i<len)	//堆排序使用完全二叉树，小标从1开始，这里转换一下
	{
		a[i+1]=array[i];
		i++;
	}
	for(n=len/2;n>0;n--)	//计算的n可以理解为完全二叉树的层数，通过这个循环，已经把顶根排到最大
	{
		setup_heap(a,n,len);
		loop++;
	}
	for(j=len;j>=2;j--)
	{
		tmp=a[1];
		a[1]=a[j];
		a[j]=tmp;
		setup_heap(a,1,j-1);
		loop++;
		swap++;
	}
	i=0;
	while(i<len)	//堆排序使用完全二叉树，小标从1开始，这里转换回来
	{
		array[i]=a[i+1];
		i++;
	}
	printf("堆排序交换%d次，循环%d次\n",swap,loop);
}
void single_array_select_sort(int *array,int len)
{
	int n;
back:
	printf("1.简单选择排序\n");
	printf("2.堆排序\n");
	printf("3.退出\n");
	printf("\n请输入数字：");
	scanf("%d",&n);
	if(n==1)
		simple_select_sort(array,len);
	else if(n==2)
		heap_sort(array,len);
	else if(n==3)
		return;
	else
		goto back;
}
/*********************************/

/***********归并排序**************/
void single_array_merge_sort(int *array,int len)
{
	printf("1.二路归并排序\n");
	printf("2.多路归并排序\n");
	printf("3.退出\n");
	printf("\n请输入数字：");
}
/*********************************/

/***********其他线性排序排序**************/
void single_array_other_sort(int *array,int len)
{
	printf("1.基数排序\n");
	printf("2.桶排序\n");
	printf("3.退出\n");
	printf("\n请输入数字：");
}
/*********************************/
void array_swap(int *orgin,int *new,int len)
{
	int i=0;
	while(i<len)
	{
		new[i]=orgin[i];
		i++;
	}
}

void all_sort_compare(int *array,int len)
{
	int a[ARRAY_MAX_LEN]={0};

	array_swap(array,a,len);
	array_bubble_sort(a,len);

	array_swap(array,a,len);
	array_quick_sort(a,len);



	array_swap(array,a,len);
	simple_insert_sort(a,len);

	array_swap(array,a,len);
	half_inserted_sort(a,len);

	array_swap(array,a,len);
	shell_sort(a,len);


	array_swap(array,a,len);
	simple_select_sort(a,len);

	array_swap(array,a,len);
	heap_sort(a,len);
}


void sort_option_array(int *array,int len)
{
	int i;
back:
	printf("1.交换排序\n");
	printf("2.插入排序\n");
	printf("3.选择排序\n");
	printf("4.归并排序\n");
	printf("5.其他排序\n");
	printf("6.各种排序对比\n");
	printf("7.退出\n");
	printf("\n请输入数字：");
	scanf("%d",&i);
	if(i==1)
		single_array_swap_sort(array,len);
	else if(i==2)
		single_array_insert_sort(array,len);
	else if(i==3)
		single_array_select_sort(array,len);
	else if(i==4)	
		return;	
	else if(i==5)	
		return;	
	else if(i==6)
		all_sort_compare(array,len);
	else if(i==7)
		return;	
	else
		goto back;	
}
/*单链表操作选项菜单*/
int single_array_option(int *array,int len)
{
	int i;
back:
	printf("\n\n\n");
	printf("==============数组选择菜单==============\n");
	printf("1.一元数组创建\n");
	printf("2.一元数组排序\n");
	printf("3.打印数组\n");
	printf("4.删除数组\n");
	printf("5.退出\n");
	printf("=======================================\n");
	printf("\n");
	printf("\n请输入数字：");
	scanf("%d",&i);
	printf("\n");
	switch(i)	
	{
		case 1:	
		back1:
			printf("1.一元数组自动创建\n");
			printf("2.一元数组手动创建\n");
			printf("3.删除一元数组\n");
			printf("4.退出\n");
			printf("请输入数字：");
			scanf("%d",&i);
			if(i==1)
				len=auto_create_single_array(array);
			else if(i==2)
				len=self_create_single_array(array);
			else if (i==3)
				len=delete_single_array(array,len);
			else if (i==4)
				goto back;
			else
			goto back1;
			break;
		case 2:	
			sort_option_array(array,len);
			break;
		case 3:	
			print_array(array,len);
			break;
		case 4:
			len=delete_single_array(array,len);
			break;
		case 5:
			return len;	
			break;
		default:
			goto back;
	}
	goto back;
}

/*
void main()
{
	int len,s,e;
	printf("请输入数组长度：\n");
	scanf("%d",&len);
	printf("请输入数据最小值：\n");
	scanf("%d",&s);
	printf("请输入数据最大值：\n");
	scanf("%d",&e);
	if(e<s)
		printf("最大值小于最小值，无法创建！");
	create_single_array(array,len,s,e);
	print_array(array,len);
}
*/
